package a00_LeetCode.LinkedList;

/**
 * @Author quan
 * @Description ！！！没看懂！！！删除链表中所有重复元素，一个都不保留
 * @Date 2023/3/25 19:13
 */
public class Num82_DuplicatesSaveNone {
    //能大概看懂，但是自己没有写
    /*public ListNode deleteDuplicates(ListNode head) {
        // 1.base case
        if(head == null || head.next == null) {
            return head;
        }
        if(head.val != head.next.val) {
            head.next = deleteDuplicates(head.next);
            return head;
        }else {
            // 头节点就是重复的节点，先处理完头节点的情况
            ListNode newHead = head.next;
            while(newHead != null && newHead.val == head.val) {
                newHead = newHead.next;
            }
            // 此时newHead一定不是待删除的结点，最终整个传入函数，返回更新后的值即可
            return deleteDuplicates(newHead);
        }
    }*/
    /**
     * 没看懂。看着代码理解：图没画出来？？？？？？？？？？？？
     */
    public ListNode deleteDuplicates(ListNode head) {
//         1.base case
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(-101);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode cur = prev.next;
        while (cur != null) {
            ListNode sec = cur.next;
            if (sec == null) {
                break;
            }
            if (cur.val != sec.val) {
                prev = prev.next;
            }else {
                // 此时cur和sec相等
                while (sec != null && cur.val == sec.val) {
                    sec = sec.next;
                }
                // 此时sec一定走到第一个和cur不相等的结点
                // prev .. sec全都是待删除的结点
                prev.next = sec;
            }
            cur = sec;
        }
        return dummyHead.next;
    }
}
